﻿/*
题目: 只出现一次的数字 III

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

https://leetcode.cn/problems/single-number-iii/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int x = 0;
        for (int i = 0; i < nums.size(); i++) {
            x ^= nums[i];
        }

        // 取出最低位的 1
        int low = 0;
        for (int i = 0; i < 32; i++) {
            if (((x >> i) & 1) == 0) {
                continue;
            }
            else {
                low = (x & (1 << i));
                break;
            }
        }

        // 根据最低位的 1 来区分这两个具体的数字
        // 根据这一位把这两个元素区分开来
        int num1 = 0, num2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if ((low & nums[i]) == 0) {
                num1 ^= nums[i];
            }
            else {
                num2 ^= nums[i];
            }
        }

        return { num1, num2 };
    }
};